package demo.practice.stack;

import java.util.PriorityQueue;

public class P4 {


    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        MedianFinder mf= new MedianFinder();
        for (int i : nums1) {
            mf.addNum(i);
        }

        for (int i : nums2) {
            mf.addNum(i);
        }

        return mf.findMedian();

    }
}


class MedianFinder {

    PriorityQueue<Integer> bigger;
    PriorityQueue<Integer> litter;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        bigger = new PriorityQueue<Integer>((i1, i2) -> i1 - i2);   //都比顶大，小顶对
        litter = new PriorityQueue<Integer>((i1, i2) -> i2 - i1);
    }

    public void addNum(int num) {
        if (bigger.size() == 0) {
            bigger.add(num);
            return;
        }

        if (num > bigger.peek()) {
            bigger.add(num);
        } else {
            litter.add(num);
        }

        while (bigger.size() - litter.size() > 1) {
            litter.add(bigger.poll());
        }

        while (litter.size() - bigger.size() > 1) {
            bigger.add(litter.poll());
        }

    }

    public double findMedian() {

//        if(bigger.size()==0&&litter.size()==0)
//            return 0.0;

        if (bigger.size() == 0 || litter.size() == 0) {
            return bigger.size() == 0 && litter.size() == 0 ? 0.0 : bigger.size() == 0 ? litter.peek() : bigger.peek();
        }

        if (bigger.size() == litter.size()) {
            return (double) (bigger.peek() + litter.peek()) / 2;
        }

        return bigger.size()> litter.size()? bigger.peek(): litter.peek();

    }
}